package TestSort;

import com.sun.scenario.effect.Brightpass;

import java.util.Random;
import java.util.Stack;

public class QuickSort {
    public static void quickSort (int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = midNumIndex(arr, left, right);
        swap(arr, index, left);
        int pivot = partitionHole(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }


    /**
     * Hoare法
     * @param arr
     * @param left
     * @param right
     * @return pivot的位置
     */
    public static int partition (int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;
        //i和j相遇才结束
        while (i < j) {
            //找到比pivot小的index
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            //找到比pivot大的index
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            //交换两个数使大的在右小的在左
            swap(arr, i, j);
        }
        //交换基准值和i，使基准在中间
        swap(arr, i, left);
        return i;
    }

    /**
     * 挖坑法
     * @param arr
     * @param left
     * @param right
     * @return pivot的位置
     */
    public static int partitionHole (int[] arr, int left, int right) {
        /**
         * 先存下arr[left]的值
         * 这样left位置被替换了也没事
         */
        int pivot = arr[left];
        while (left < right) {
            //找到比pivot小的值
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //直接将小的值替换到left
            arr[left] = arr[right];
            //找到比pivot大的值
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //直接将大的值替换到right
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

    /**
     * 前后指针法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partitionPointer (int[] arr, int left, int right) {
        //prev存的是pivot
        int prev = left;
        int cur = prev + 1;
        while (cur < right) {
            if (arr[cur++] <= arr[left] && arr[prev] != arr[cur]) {
                prev++;
                swap(arr, prev, cur);
            }
        }
        swap(arr, prev, left);
        return prev;
    }


    /**
     * 得到中间大的数坐标
     */
    public static int midNumIndex (int[] arr, int left, int right) {
        int mid = (left + right) >> 1;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) {
                return left;
            } else {
                if (arr[mid] < arr[right]) {
                    return mid;
                } else {
                    return right;
                }
            }
        } else {
            if (arr[mid] < arr[right]) {
                return right;
            } else {
                if (arr[mid] < arr[left]) {
                    return mid;
                } else {
                    return left;
                }
            }
        }
    }

    public static void swap (int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    /**
     * 非递归实现 快速排序
     */
    public static void quickSort(int[] array) {

        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*log n
        int index = midNumIndex(array,left,right);
        swap(array,left,index);

        //得到第一次的基准值
        int pivot = partitionHole(array,left,right);

        //pivot不和left或right贴着时候入栈
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot - 1);
        }

        if(pivot < right-1) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.empty()) {

            //循环执行得到左右基准的
            right = stack.pop();
            left = stack.pop();
            index = midNumIndex(array,left,right);
            swap(array,left,index);
            pivot = partition(array,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right-1) {
                stack.push(pivot + 1);
                stack.push(right);
            }

        }
    }

    public static void main1(String[] args) {
        int[] arr = new int[10_0000];
        Random random = new Random();
        int i = 0;
        while (i < arr.length) {
            arr[i++] = random.nextInt(10_0000);
        }
        quickSort(arr, 0, arr.length - 1);
        i = 0;
        while (i < arr.length) {
            System.out.print(arr[i++] + " ");
        }
    }
}
